package Niuke;

class MagicDictionary {
    TireNode root;

    public MagicDictionary() {
        root=new TireNode();
    }

    public void buildDict(String[] dictionary) {
        for (String s:dictionary){
            char[] chars = s.toCharArray();
            TireNode p=root;
            for (int i=0;i<chars.length;i++){
                if (p.child[chars[i]-'a']==null)
                    p.child[chars[i]-'a']=new TireNode();
                p=p.child[chars[i]-'a'];
            }
            p.finished=true;
        }
    }

    public boolean search(String searchWord) {
        return dfs(searchWord,root,0,false);
    }

    public boolean dfs(String searchWord,TireNode node,int pos,boolean modified){
        if (pos==searchWord.length())
            return node.finished&&modified;
        int idx=searchWord.charAt(pos)-'a';
        //not change
        if (node.child[idx]!=null){
            if (dfs(searchWord,node.child[idx],pos+1,modified))
                return true;
        }
        //change
        if (!modified){
            for (int i=0;i<26;i++){
                if (i!=idx&&node.child[i]!=null) {
                    if (dfs(searchWord,node.child[i],pos+1,true)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    class TireNode{
        boolean finished;
        TireNode[] child;

        TireNode(){
            child=new TireNode[26];
            finished=false;
        }
    }
}
